//
//  Problem96.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/2/24.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 96. 不同的二叉搜索树
 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

 示例:
     输入: 3
     输出: 5
     解释:
     给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

    1         3     3      2      1
     \       /     /      / \      \
      3     2     1      1   3      2
     /     /       \                 \
    2     1         2                 3
 */
@objcMembers class Problem96: NSObject {
    func solution() {
        print(numTressClearAlloc(3))
        print(numTressClearAlloc(4))
    }
    
    /*
     动态规划
     1: 创建一个数组dp[n][n]
     2: dp[i][j]: i~j 组成的二叉搜索树个数 （i<=j）
     3: dp[0][n]: r(1) + r(1) + r(2) + ... + r(n)
     4: r(1): dp[1][n]
        r(2): dp[1][1] * dp[3][n]
     */
    func numTrees(_ n: Int) -> Int {
        if n <= 2 {             // 特例：
            return n
        }
        
        var dp = Array(repeating: Array(repeating: 1, count: n+1), count: n+1)
        for i in 1..<n {        // 特例：i~i+1 = 2
            dp[i][i+1] = 2
        }
        // 倒叙循环
        var i = n - 2
        while i > 0 {
            for j in i+2...n {
                var result = 0
                for k in i...j {
                    if k == j {
                        result += dp[i][j-1]
                    } else if k == i {
                        result += dp[i+1][j]
                    } else {
                        result += dp[i][k-1] * dp[k+1][j]
                    }
                }
                dp[i][j] = result
            }
            i -= 1
        }
        
        for i in 0...n {
            print(dp[i])
        }
        return dp[1][n]
    }
    
    /*
     优化：
     1: 使用一个数组
     2: 发送 3个连续的个数 都是一样
     */
    func numTressClearAlloc(_ n: Int) -> Int {
        if n <= 2 {             // 特例：
            return n
        }
        
        var dp = Array(repeating: 1, count: n+1)
        dp[0] = 0
        dp[1] = 1       // 特例：n = 1 只有1个
        dp[2] = 2       // 特例：n = 2 只有2个
        for i in 3...n {        // 特例：i~i+1 = 2
            var result = 0
            for j in 1...i {
                if j == i {
                    result += dp[j-1]
                } else if j == 1 {
                    result += dp[i-1]
                } else {
                    result += dp[j-1] * dp[i-j]
                }
                
            }
            dp[i] = result
        }
        
        return dp[n]
    }
}
